The present invention relates to chewing gum. More specifically, this invention relates to improved formulations for chewing gum bases possessing such polymeric networks that microcrystalline domains act as network junctions and each junction is chemically bonded to an amorphous polymeric domains. The microcrystalline domains have melting point greater than 20° C. and the microcrystalline domain size is in the range of 0.01˜100 μm. The amorphous polymer domains typically have glass transition temperatures less than 37° C. Preferably, gum bases with the above polymeric networks contain block copolymers having at least two different component polymeric blocks. In the present invention, the copolymer includes at least one soft polymeric block and at least two hard crystallizable polymeric blocks having a melting point greater than 20° C. Chewing gums prepared from the inventive gum bases may form cuds which have improved removability when attached to environmental surfaces.